{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 3 Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1\n",
    "We must show that $\\langle\\cdot,\\cdot\\rangle$ is a bilinear, symmetric, positive definite map.\n",
    "\n",
    "It is a calculation to show that $\\langle \\alpha x + \\beta x', y \\rangle = \\alpha \\langle x,y\\rangle + \\beta \\langle x',y\\rangle$, and similarly for the second argument, and so $\\langle\\cdot,\\cdot\\rangle$ is bilinear.\n",
    "\n",
    "We have $\\langle y,x\\rangle = y_1x_1 - (y_1x_2+y_2x_1)+2y_2x_2 = \\langle x,y\\rangle$ indeed, so we have symmetry.\n",
    "\n",
    "Finally, $\\langle x,x \\rangle = x_1^2 - 2x_1x_2+2x_2^2 = (x_1-x_2)^2 + x_2^2$. Clearly, if $x=0$, then $\\langle x,x \\rangle = 0$. If $x\\neq 0$, then either $x_2 \\neq 0$, in which case $\\langle x,x \\rangle > 0$; or $x_2=0$ with $x_1 \\neq 0$, so $\\langle x,x \\rangle > 0$ again (since it's the sum of two squares of real numbers). Therefore $\\langle \\cdot , \\cdot \\rangle$ is an inner product indeed!\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2\n",
    "Observe that $\\left\\langle \\begin{bmatrix}\n",
    "1\\\\0\n",
    "\\end{bmatrix} , \\begin{bmatrix}\n",
    "0\\\\1\n",
    "\\end{bmatrix} \\right\\rangle = 0$, but $\\left\\langle \\begin{bmatrix}\n",
    "0\\\\1\n",
    "\\end{bmatrix} , \\begin{bmatrix}\n",
    "1\\\\0\n",
    "\\end{bmatrix} \\right\\rangle = 1$, so $\\langle \\cdot, \\cdot \\rangle$ is not symmetric, and thus not an inner product. (Observe that the matrix $A$ is not a symmetric matrix!)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3\n",
    "\n",
    "We have $d(x,y) = \\sqrt{\\langle(x-y),(x-y)\\rangle} = \\sqrt{\\left\\langle\\begin{bmatrix}\n",
    "2\\\\3\\\\3\n",
    "\\end{bmatrix},\\begin{bmatrix}\n",
    "2\\\\3\\\\3\n",
    "\\end{bmatrix}\\right\\rangle}$.\n",
    "\n",
    "### Part a\n",
    "\n",
    "Thus $d(x,y) = \\sqrt {22}$.\n",
    "\n",
    "### Part b\n",
    "Here, $d(x,y) = \\sqrt{47}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4\n",
    "We have that the angle $\\omega$ between the two vectors is given by $\\omega = \\cos^{-1}\\left(\\frac{\\langle x, y \\rangle}{\\lVert x\\rVert\\lVert y\\rVert}\\right)$, where $\\lVert x \\rVert = \\sqrt{\\langle x,x\\rangle}$.\n",
    "\n",
    "### Part a\n",
    "Here, $\\lVert x \\rVert = \\sqrt 5$ and $\\lVert y \\rVert = \\sqrt 2$. Also, $\\langle x,y \\rangle = -3$. Thus $\\omega = \\cos^{-1}\\left(\\frac{-3}{\\sqrt{10}}\\right) = 2.8198$.\n",
    "\n",
    "### Part b\n",
    "Now, $\\lVert x \\rVert = \\sqrt {18}$ and $\\lVert y \\rVert = \\sqrt 7$. Also, $\\langle x,y \\rangle = -11$. Thus $\\omega = \\cos^{-1}\\left(\\frac{-11}{\\sqrt{126}}\\right) = \\cos^{-1}\\left(\\frac{-11\\sqrt{14}}{42}\\right)$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5\n",
    "### Part a\n",
    "Let $v_1, \\dots, v_4$ be the four vectors defined in the question. Observe that $rank[v_1|v_2|v_3|v_4]=3$. Moreover, $rank[v_1|v_2|v_3]=3$, so these three vectors form a basis of $U$. Let $B$ be this matrix of basis vectors, i.e.~$B=[v_1|v_2|v_3]$.\n",
    "\n",
    "Now we compute $B^{\\mathsf{T}}B = \\begin{bmatrix}\n",
    "9&9&0\\\\\n",
    "9&16&-14\\\\\n",
    "0&-14&31\n",
    "\\end{bmatrix}$ and $B^{\\mathsf{T}}x = \\begin{bmatrix}\n",
    "9\\\\23\\\\-25\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "Next, we solve $B^{\\mathsf{T}}B\\lambda = B^{\\mathsf{T}}x$ for $\\lambda$. Using Gaussian elimination, we obtain $\\lambda = \\begin{bmatrix}-3\\\\\n",
    "4\\\\\n",
    "1\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "Finally, $\\pi_U(x)$ is given by $B\\lambda = \\begin{bmatrix}\n",
    "1\\\\-5\\\\-1\\\\-2\\\\3\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "### Part b\n",
    "By construction, $d(x,U) = d(x,\\pi_U(x))$. This is given by $\\lVert x-\\pi_U(x) \\rVert = \\begin{Vmatrix}-2\\\\-4\\\\0\\\\6\\\\-2\n",
    "\\end{Vmatrix}$.\n",
    "\n",
    "This norm is given by the square root of the dot product of the vector with itself, so $d(x,U) = \\sqrt{60}=2\\sqrt{15}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 6\n",
    "### Part a\n",
    "We require $\\langle e_1, e_2-\\pi_U(e_2)\\rangle = 0$ and $\\langle e_3, e_2-\\pi_U(e_2)\\rangle = 0$. That is to say, $\\left\\langle \\begin{bmatrix}\n",
    "1\\\\0\\\\0\n",
    "\\end{bmatrix}, \\begin{bmatrix}-\\lambda_1\\\\1\\\\ -\\lambda_2\n",
    "\\end{bmatrix} \\right\\rangle = 0$, and $\\left\\langle \\begin{bmatrix}\n",
    "0\\\\0\\\\1\n",
    "\\end{bmatrix}, \\begin{bmatrix}-\\lambda_1\\\\1\\\\ -\\lambda_2\n",
    "\\end{bmatrix} \\right\\rangle = 0$.\n",
    "\n",
    "Computing the first gives us $\\lambda_1=\\frac12$, while the second gives $\\lambda_2 = -\\frac12$.\n",
    "\n",
    "Therefore, $\\pi_U(e_2) = \\begin{bmatrix}\n",
    "\\frac12 \\\\ 0\\\\ -\\frac12\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "### Part b\n",
    "We have $d(e_2,U) = \\lVert e_2-\\pi_U(e_2) \\rVert = \\sqrt{\\left\\langle \\begin{bmatrix}-\\frac12 \\\\ 1\\\\ \\frac12\\end{bmatrix},\\begin{bmatrix}-\\frac12 \\\\ 1\\\\ \\frac12\\end{bmatrix}\\right\\rangle} = 1$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 7\n",
    "### Part a\n",
    "Let $x\\in V$. Observe that $((id-\\pi)\\circ(id-\\pi))(x) = (id-\\pi)(x-\\pi(x)) = (x-\\pi(x))-(\\pi(x)-\\pi^2(x)) = x-2\\pi(x)+\\pi^2(x)$. Hence $(id -\\pi)$ is a projection if and only if $x-\\pi(x) = x-2\\pi(x)+\\pi^2(x)$. This happens if and only if $\\pi(x) = \\pi^2(x)$, that is to say, where $\\pi$ is a projection.\n",
    "\n",
    "### Part b\n",
    "We have $Im(id-\\pi) = \\{(id-\\pi)(x):x\\in V\\} = \\{x-\\pi(x):x\\in V\\}$. Observe that $\\pi(x-\\pi(x)) = \\pi(x)-\\pi^2(x) = 0$, since $\\pi$ is a projection. Thus, $Im(id-\\pi)\\subseteq\\ker\\pi$.\n",
    "\n",
    "Now, suppose $k\\in \\ker \\pi$. Then $k-\\pi(k)=k$, so $k\\in Im(id-\\pi)$. Thus $\\ker\\pi\\subseteq Im(id-\\pi)$. Therefore, we have that $Im(id-\\pi) = \\ker\\pi$. $\\lozenge$\n",
    "\n",
    "We have that $\\ker(id-\\pi) = \\{x\\in V : (id-\\pi)(x) = 0\\} = \\{x\\in V : x=\\pi(x)\\}$. Clearly, $\\ker(id-\\pi)\\subseteq Im\\pi$.\n",
    "\n",
    "Take $x\\in Im\\pi$. Then there exists some $y\\in V$ such that $\\pi(y)=x$. Observe that $(id-\\pi)(x) = x-\\pi(x) = \\pi(y)-\\pi^2(y) = 0$, since $\\pi$ is a projection. Hence $Im\\pi\\subseteq\\ker(id-\\pi)$. Therefore we have that $\\ker(id-\\pi) = Im\\pi$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 8\n",
    "I will assume we use the standard dot product as our inner product. Firstly, let's get an orthogonal basis, then we can simply divide by the magnitude of each vector to get our orthonormal basis.\n",
    "\n",
    "Since $b_1$ is our first vector, there is nothing to do for now. To get the second vector in our basis, we need a vector, $b_2'$, perpendicular to $b_1$, such that $span(b_1,b_2) = span (b_1, b_2')$. This is given by $b_2' = b_2 - \\pi_{span(b_1)}(b_2)$.\n",
    "\n",
    "Now, $\\pi_{span(b_1)}(b_2) = \\frac{b_1b_1^\\mathsf{T}}{\\lVert b_1 \\rVert^2} b_2 = \\frac{1}{3} \\begin{bmatrix}\n",
    "1&1&1\\\\\n",
    "1&1&1\\\\\n",
    "1&1&1\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}-1\\\\2\\\\0\n",
    "\\end{bmatrix} = \\frac{1}{3}\\begin{bmatrix}\n",
    "1\\\\1\\\\1\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "Therefore, $b_2' = \\begin{bmatrix}-\\frac43 \\\\ \\frac53 \\\\ -\\frac13\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "Hence, our orthonormal basis, $C$, is given by $C=\\left\\{\\frac{1}{\\sqrt3}\\begin{bmatrix}\n",
    "1\\\\1\\\\1\n",
    "\\end{bmatrix} , \\frac{1}{\\sqrt42}\\begin{bmatrix}-4\\\\5\\\\-1\n",
    "\\end{bmatrix}\\right\\}$.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 9\n",
    "### Part a\n",
    "Take $x = (x_1,\\dots, x_n)$ and $y=(1,\\dots,1)$. The Cauchy-Schwarz tells us that $\\langle x, y \\rangle \\leq \\lVert x \\rVert \\lVert y \\rVert$, so we have $\\sum_{i=1}^{n}x_i \\leq \\sqrt{\\sum_{i=1}^{n}{x_i^2}}\\sqrt{n}$. Using $\\sum x_i = 1$ and squaring both sides (noting that both sides are indeed positive!)~gives us the required result.\n",
    "\n",
    "### Part b\n",
    "Take $x = \\left(\\sqrt{x_1},\\dots, \\sqrt{x_n}\\right)$ and $y = \\left(\\frac{1}{\\sqrt{x_1}},\\dots,\\frac{1}{\\sqrt{x_n}}\\right)$. Then Cauchy-Schwarz gives us that $n \\leq \\sqrt{\\sum x_i} \\sqrt{\\sum \\frac{1}{x_i}}$. The same trick as before gives us the required result.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 10\n",
    "\n",
    "I will assume we need to rotate these vectors anticlockwise. A rotation about an angle $\\theta$ is given by the matrix $\\begin{bmatrix}\n",
    "\\cos\\theta&-\\sin\\theta\\\\\n",
    "\\sin\\theta&\\cos\\theta\n",
    "\\end{bmatrix}$. Thus for $\\theta=30^\\circ$, we have $R=\\begin{bmatrix}\n",
    "\\frac{\\sqrt{3}}{2}&-\\frac{1}{2}\\\\\n",
    "\\frac12 & \\frac{\\sqrt3}{2}\n",
    "\\end{bmatrix} = \\frac12 \\begin{bmatrix}\n",
    "\\sqrt3 & -1\\\\\n",
    "1&\\sqrt3\n",
    "\\end{bmatrix}$.\n",
    "\n",
    "Therefore, $Rx_1 = \\frac12 \\begin{bmatrix}\n",
    "2\\sqrt3-3\\\\2+3\\sqrt3\n",
    "\\end{bmatrix}$ and $Rx_2 = \\frac12 \\begin{bmatrix}\n",
    "1\\\\-\\sqrt3\n",
    "\\end{bmatrix}$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
